Routing algorithms play a role of paramount importance in wireless ad hoc and sensor networks, as their efficiency can significantly affect the overall system performance. Such schemes are required each time a node has data to deliver to a destination that is too far to be reached by way of a single transmission, and their role is twofold. On one hand, the routing algorithms have to locate the desired node within the network and identify a path (that is, a sequence of neighboring terminals) that can be used to deliver packets to such a target. On the other hand, a routing procedure has to react whenever a given path is no longer available by providing an alternative source-destination connection (route recovery mechanism).
Existing routing algorithms include static and dynamic approaches. In the former case, the sink node is tracked by way of a route construction procedure whose outcome is a single path from the source to the destination. Once such a route has been identified, it is used to forward data. The source sends the data packet addressed to the destination to the first node in the discovered route. Such a node, then, forwards the received packet to the following node in the sequence, and so on, until the destination receives the information. Static routing does not require any geographic information on terminal locations, and thus it is suitable for all the applications where node positions cannot be inferred. However, this approach triggers a route recovery procedure as soon as one of the nodes along the built forwarding sequence is no longer available. This may happen, for example, because of harsh channel conditions, mobility and/or node failures. In ad hoc networks, for instance, terminals that move around represent a common situation. In these conditions, whenever a node moves out of the coverage range of its predecessor in a routing path, the solution offered by static routing does not work anymore.
Another scenario that may severely suffer if a single path from the source to the destination is provided is represented by wireless sensor networks (WSNs). Here, the terminals typically have a limited life, constrained by the duration of their battery. Due to this, sensor nodes usually have a very short duty cycle in order to save energy, and may be unavailable to communications for most of the time unless a specific scheduling procedure is provided (which is a non-trivial task in a fully distributed network). In such a setting, terminals may easily invalidate a previously tracked route because of energy depletion or sleep-mode induced inactivity. Whenever a tracked route fails, static routing triggers a procedure to identify a new path to reach the destination. These procedures significantly increase costs in terms of energy consumption, and negatively affect the overall quality of service (QoS), for instance in terms of latency. One of the best known existing static routing algorithms is Ad hoc On-demand Distance Vector routing (AODV) that handles both the route construction and the route recovery procedures by flooding control messages through the network.
A completely different approach is followed by dynamic routing algorithms, such as Geographic Random Forwarding (GeRaF), which have been proposed for networks where geographic information is available at terminals (for example, by way of a global positioning system (GPS)). In such an algorithm, all of the nodes are aware of the location of the destination, and a route construction procedure to track this node is not needed. A node that has data to forward simply broadcasts a request packet to its neighbors. The receivers of this message infer the advancement that they offer towards the sink by exploiting topological knowledge and contend among each other to elect the next hop closest to the target. Once the next hop has been chosen, data are sent to this node, and the procedure is iterated until the destination is eventually reached. As opposed to algorithms like AODV, the dynamic approach does not divide the routing algorithm in path construction and data forwarding, but rather chooses, step by step, a next hop and immediately sends information without knowing in advance the complete route that will be followed to eventually reach the destination. Therefore, even if a node that may be used for forwarding data is not available, another terminal can take its place in a seamless way. This capability of dynamic strategies of not relying on a single path when routing data from a source to a destination strongly enhances the robustness against impairments that typically affect static routing. However, the need for geographic information limits the applicability of such solutions, due to the cost and complexity of location systems.